package q142_detectCycle;

import CommonClass.Common.ListNode;

public class Solution {
    public static void main(String[] args) {

    }
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        // 注意， 为了维持等式成立，这里的快慢指针要从同一个起点出发
        // 这样才能保证快指针始终都是慢指针走的长度的两倍
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                ListNode pin = head;
                while (pin != slow){
                    pin = pin.next;
                    slow = slow.next;
                }
                return pin;
            }
        }
        return null;
    }
    public ListNode detectCycle_2(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        // 注意，为了维持等式成立，这里的快慢指针要保证快指针始终都是慢指针走的长度的两倍
        ListNode fast = head.next.next, slow = head.next;
        while (fast != slow){
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode pin = head;
        while (pin != slow) {
            pin = pin.next;
            slow = slow.next;
        }

        return pin;
    }
}
